package cn.pugle.oj.leetcode;

import cn.pugle.oj.catalog.GraphProblem;

/**
 * 有多少个朋友圈
 * uf解法 并查集
 * https://zxi.mytechroad.com/blog/data-structure/sp1-union-find-set/
 *
 * @author tzp
 * @since 2020/11/3
 */
public class LC547_1 implements GraphProblem {
    static class UF {
        int[] parent;
        int[] rank;

        public UF(int n) {
            parent = new int[n];
            rank = new int[n];
            for (int i = 0; i < n; i++) {
                parent[i] = i;
                rank[i] = 1;
            }
        }

        public int find(int x) {
            while (parent[x] != x) {
                parent[x] = parent[parent[x]];//find的时候进行压缩path
                x = parent[x];
            }
            return x;
        }

        public boolean union(int x, int y) {
            int xp = find(x);
            int yp = find(y);
            if (xp == yp) return false;
            if (rank[xp] < rank[yp]) {//xprank小, 把xp接到yp下面
                parent[xp] = yp;
            } else if (rank[xp] > rank[yp]) {
                parent[yp] = xp;
            } else {//==, rank+1
                parent[xp] = yp;
                rank[yp]++;
            }
            return true;
        }
    }

    public int findCircleNum(int[][] M) {
        UF uf = new UF(M.length);
        int size = M.length;
        for (int i = 0; i < M.length; i++) {
            for (int j = i + 1; j < M.length; j++) {
                if (M[i][j] == 1) {
                    if (uf.union(i, j)) size--;//不用遍历uf的组数量了, 直接用这个--数得到结果
                }
            }
        }
        return size;
    }

    public static void main(String[] args) {
        System.out.println(new LC547_1());
    }
}
